package com.lw.leetcode.back.b;

/**
 * 547. 省份数量
 * 剑指 Offer II 116. 省份数量
 *
 * @Author liw
 * @Date 2021/8/11 21:57
 * @Version 1.0
 */
public class FindCircleNum {

    public static void main(String[] args) {
        FindCircleNum test = new FindCircleNum();
        int[][] arr = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
        int circleNum = test.findCircleNum(arr);
        System.out.println(circleNum);
    }

    int[][] isConnected;

    public int findCircleNum(int[][] isConnected) {
        int length = isConnected.length;
        this.isConnected = isConnected;
        int[] arr = new int[length];
        int count = 0;
        for (int i = 0; i < length; i++) {
            if (arr[i] == 1) {
                continue;
            }
            arr[i] = 1;
            count++;
            find(i, arr, length);
        }
        return count;
    }

    private void find(int index, int[] arr, int length) {
        int[] ints = isConnected[index];
        for (int i = 0; i < length; i++) {
            if (ints[i] == 0 || arr[i] == 1) {
                continue;
            }
            arr[i] = 1;
            find(i, arr, length);
        }
    }

}
